package sort;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yi
 * Date: 2024-07-29
 * Time: 23:39
 */
public class HeapSort {

    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array,int parent, int usedSize) {
        int child = parent*2+1;
        while(child < usedSize) {
            if (child+1 < usedSize && array[child + 1] > array[child]) {
                child = child + 1;
            }
            if (array[parent] < array[child]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }
    public static void sort(int[] array) {
        createHeap(array);
        int end = array.length - 1;
        while(end > 0){
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }
}
